比對List和SortedList

比對容器

• List
• SortedList

比較方法

• 資料放入容器的時間
• 演算法處理時間

開始測試

演算法 - Binary Search

List

public static int Search_List(List<int> list, int num)
{
    int left = 0, right = list.Count() - 1;
    while (left <= right)
    {
        int middle = (right + left) / 2;

        if (list[middle] == num)
            return middle;

        if (list[middle] > num)
            right = middle - 1;
        else
            left = middle + 1;
    }
    return -1;
}

SortedList

public static int Search_SortedList(SortedList<int, int> sortedSet, int num)
{
    int left = 0, right = sortedSet.Count() - 1;
    while (left <= right)
    {
        int middle = (right + left) / 2;

        if (sortedSet.Keys[middle] == num)
            return middle;

        if (sortedSet.Keys[middle] > num)
            right = middle - 1;
        else
            left = middle + 1;
    }
    return -1;
}

測試流程

List

static void ListTest(int testNumber, int targetNumber)
{
    Console.WriteLine("=====List Test=====");
    List<int> list = new List<int>();
    Stopwatch stopwatch = new Stopwatch();
    stopwatch.Start();
    for (int i = testNumber; i >= 0; i--)
    {
        list.Add(i);
    }
    stopwatch.Stop();
    Console.WriteLine($"Add data cost time : {stopwatch.ElapsedMilliseconds}");

    stopwatch.Restart();
    list.Sort();
    var data = BinarySearcher.Search_List(list, targetNumber);
    stopwatch.Stop();

    Console.WriteLine($"Find Result = {data}");
    Console.WriteLine($"Search Time : {stopwatch.ElapsedMilliseconds}ms");
}

SortedList

static void SortedListTest(int testNumber, int targetNumber)
{
    Console.WriteLine("=====SortedList Test=====");
    Stopwatch stopwatch = new Stopwatch();
    SortedList<int, int> sortedList = new SortedList<int, int>();
    stopwatch.Start();
    for (int i = testNumber; i >= 0; i--)
    {
        sortedList.Add(i, i);
    }
    stopwatch.Stop();
    Console.WriteLine($"Add data cost time : {stopwatch.ElapsedMilliseconds}");

    stopwatch.Restart();
    var data = BinarySearcher.Search_SortedList(sortedList, targetNumber);
    stopwatch.Stop();

    Console.WriteLine($"Find Result = {data}");
    Console.WriteLine($"Search Time : {stopwatch.ElapsedMilliseconds}ms");
}

開始測試

List<int> list = new List<int>();
int testNumber = 500000;
int targetNumber = 1500;
Console.WriteLine($"Test Number = {testNumber}");
ListTest(testNumber, targetNumber);
Console.WriteLine();
SortedListTest(testNumber, targetNumber);
Console.WriteLine();
Console.WriteLine();

testNumber = 2000;
Console.WriteLine($"Test Number = {testNumber}");
ListTest(testNumber, targetNumber);
Console.WriteLine();
SortedListTest(testNumber, targetNumber);

測試結果

小結

Binary Search必須要先排序

• List塞值不排，要做演算法時才排
• SortdeList邊塞邊排，可直接使用驗算法

先看2000筆資料的比對
因為數值少，在毫秒內就處理完了，沒感覺。

不過在加大為500000筆資料後就有很大差距了
SortedList塞資料塞半天，超級放浪費時間
不過搜尋到是han快，畢竟已經排好了
List塞值很快，要做演算法前先才排序，所以浪費點時間。

依結果來看，用List就好了。￣ 3￣▂ξ

=============新增測試============
假如把原本的塞值testNumber到0改成0到testNumber的話

for (int i = testNumber; i >= 0; i--)
{
    sortedList.Add(i, i);
}

改成

for (int i = 0; i < testNumber; i++)
{
    sortedList.Add(i, i);
}

結果如下 :

因為本來就排好排滿了，SortedList塞值變快很多，除非需要不斷的大量搜尋，不然...

依結果來看，還是用List就好了。￣ 3￣▂ξ

=============又新增測試了============
後來想到List只要Sort一次就好，不用每次都去Sort，所以測試了只Sort一次，之後的搜尋就直接用這個List去跑演算法。
跑出來結果Search Time大概會降到9ms左右

依結果來看，還是用List就好了。￣ 3￣▂ξ￣ 3￣▂ξ

新手發文，若有錯誤的地方請不吝色的指正，謝謝。